#include<iostream>
using namespace std;
#include<queue>
#include<vector>
#include<unordered_map>
#include<unordered_set>
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, bool> find;
        for (auto& e : wordList)
            find[e] = false;
        queue<string> que;
        que.push(beginWord);
        int sum = 1, n = beginWord.size();
        while (que.size()) {
            int size = que.size();
            ++sum;
            while (size--) {
                string& str = que.front();
                for (int i = 0; i < n; ++i) {
                    char now = str[i];
                    for (int j = 0; j < 26; ++j) {
                        if ('a' + j == now)
                            continue;
                        str[i] = 'a' + j;
                        if (find.count(str)) {
                            if (str == endWord)
                                return sum;
                            else if (find[str] == false) {
                                    que.push(str);
                                    find[str] = true;
                            }
                        }
                        str[i] = now;
                    }
                }
                que.pop();
            }
        }
        return 0;
    }
};
int main() {
    string bein = "hit", end = "cog";
    vector<string>  str = {"hot", "dot", "dog", "lot", "log", "cog"};
    Solution().ladderLength(bein, end, str);
}